From 06f37a09035e8b8a1b9e9f3b538fa1f0d2c63fdf Mon Sep 17 00:00:00 2001 From: Alex Crichton Date: Wed, 28 Jan 2015 21:50:06 -0800 Subject: [PATCH] Forbid cyclic dependencies Re-jigger some code in the resolver and refactor a little bit to get the ordering of checks right to forbid cyclic dependencies from ever reaching the backend. Closes #834 --- src/cargo/core/registry.rs | 6 +- src/cargo/core/resolver/mod.rs | 123 ++++++++++++++++----------- src/cargo/ops/cargo_compile.rs | 2 - src/cargo/ops/cargo_read_manifest.rs | 1 - src/cargo/ops/cargo_rustc/mod.rs | 5 +- src/cargo/util/graph.rs | 6 +- tests/test_cargo_compile.rs | 35 +++++++- tests/test_cargo_freshness.rs | 1 + 8 files changed, 112 insertions(+), 67 deletions(-) diff --git a/src/cargo/core/registry.rs b/src/cargo/core/registry.rs index 2ff375e38..281e097f7 100644 --- a/src/cargo/core/registry.rs +++ b/src/cargo/core/registry.rs @@ -15,9 +15,6 @@ pub trait Registry { impl Registry for Vec { fn query(&mut self, dep: &Dependency) -> CargoResult> { - debug!("querying for {:?}, summaries={:?}", dep, - self.iter().map(|s| s.get_package_id()).collect::>()); - Ok(self.iter().filter(|summary| dep.matches(*summary)) .map(|summary| summary.clone()).collect()) } @@ -83,8 +80,7 @@ impl<'a, 'b> PackageRegistry<'a, 'b> { } pub fn get(&mut self, package_ids: &[PackageId]) -> CargoResult> { - log!(5, "getting packags; sources={}; ids={:?}", self.sources.len(), - package_ids); + log!(5, "getting packages; sources={}", self.sources.len()); // TODO: Only call source with package ID if the package came from the // source diff --git a/src/cargo/core/resolver/mod.rs b/src/cargo/core/resolver/mod.rs index 5ab0149ba..10c81338e 100644 --- a/src/cargo/core/resolver/mod.rs +++ b/src/cargo/core/resolver/mod.rs @@ -131,28 +131,44 @@ struct Context { /// Builds the list of all packages required to build the first argument. pub fn resolve(summary: &Summary, method: Method, registry: &mut Registry) -> CargoResult { - log!(5, "resolve; summary={:?}", summary); + log!(5, "resolve; summary={}", summary.get_package_id()); + let summary = Rc::new(summary.clone()); - let mut cx = Box::new(Context { + let cx = Box::new(Context { resolve: Resolve::new(summary.get_package_id().clone()), activations: HashMap::new(), visited: Rc::new(RefCell::new(HashSet::new())), }); let _p = profile::start(format!("resolving: {:?}", summary)); - cx.activations.insert((summary.get_name().to_string(), - summary.get_source_id().clone()), - vec![Rc::new(summary.clone())]); - match try!(activate(cx, registry, summary, method)) { - Ok(cx) => Ok(cx.resolve), + match try!(activate(cx, registry, &summary, method)) { + Ok(cx) => { + debug!("resolved: {:?}", cx.resolve); + Ok(cx.resolve) + } Err(e) => Err(e), } } fn activate(mut cx: Box, registry: &mut Registry, - parent: &Summary, + parent: &Rc, method: Method) -> CargoResult>> { + // Dependency graphs are required to be a DAG, so we keep a set of + // packages we're visiting and bail if we hit a dupe. + let id = parent.get_package_id(); + if !cx.visited.borrow_mut().insert(id.clone()) { + return Err(human(format!("cyclic package dependency: package `{}` \ + depends on itself", id))) + } + + // If we're already activated, then that was easy! + if flag_activated(&mut *cx, parent, &method) { + cx.visited.borrow_mut().remove(id); + return Ok(Ok(cx)) + } + debug!("activating {}", parent.get_package_id()); + // Extracting the platform request. let platform = match method { Method::Required(_, _, _, platform) => platform, @@ -162,7 +178,7 @@ fn activate(mut cx: Box, // First, figure out our set of dependencies based on the requsted set of // features. This also calculates what features we're going to enable for // our own dependencies. - let deps = try!(resolve_features(&mut *cx, parent, method)); + let deps = try!(resolve_features(&mut *cx, &**parent, method)); // Next, transform all dependencies into a list of possible candidates which // can satisfy that dependency. @@ -185,7 +201,40 @@ fn activate(mut cx: Box, a.len().cmp(&b.len()) }); - activate_deps(cx, registry, parent, platform, deps.as_slice(), 0) + Ok(match try!(activate_deps(cx, registry, &**parent, platform, &*deps, 0)) { + Ok(cx) => { + cx.visited.borrow_mut().remove(parent.get_package_id()); + Ok(cx) + } + Err(e) => Err(e), + }) +} + +// Activate this summary by inserting it into our list of known activations. +// +// Returns if this summary with the given method is already activated. +fn flag_activated(cx: &mut Context, + summary: &Rc, + method: &Method) -> bool { + let id = summary.get_package_id(); + let key = (id.get_name().to_string(), id.get_source_id().clone()); + let prev = cx.activations.entry(key).get().unwrap_or_else(|e| { + e.insert(Vec::new()) + }); + if !prev.iter().any(|c| c == summary) { + cx.resolve.graph.add(id.clone(), &[]); + prev.push(summary.clone()); + return false + } + debug!("checking if {} is already activated", summary.get_package_id()); + let features = match *method { + Method::Required(_, features, _, _) => features, + Method::Everything => return false, + }; + match cx.resolve.features(id) { + Some(prev) => features.iter().all(|f| prev.contains(f)), + None => features.len() == 0, + } } fn activate_deps<'a>(cx: Box, @@ -237,50 +286,20 @@ fn activate_deps<'a>(cx: Box, log!(5, "{}[{}]>{} trying {}", parent.get_name(), cur, dep.get_name(), candidate.get_version()); let mut my_cx = cx.clone(); - let early_return = { - let my_cx = &mut *my_cx; - my_cx.resolve.graph.link(parent.get_package_id().clone(), - candidate.get_package_id().clone()); - let prev = match my_cx.activations.entry(key.clone()) { - Occupied(e) => e.into_mut(), - Vacant(e) => e.insert(Vec::new()), - }; - if prev.iter().any(|c| c == candidate) { - match cx.resolve.features(candidate.get_package_id()) { - Some(prev_features) => { - features.iter().all(|f| prev_features.contains(f)) - } - None => features.len() == 0, - } - } else { - my_cx.resolve.graph.add(candidate.get_package_id().clone(), &[]); - prev.push(candidate.clone()); - false - } - }; + my_cx.resolve.graph.link(parent.get_package_id().clone(), + candidate.get_package_id().clone()); - let my_cx = if early_return { - my_cx - } else { - // Dependency graphs are required to be a DAG. Non-transitive - // dependencies (dev-deps), however, can never introduce a cycle, so - // we skip them. - if dep.is_transitive() && - !cx.visited.borrow_mut().insert(candidate.get_package_id().clone()) { - return Err(human(format!("cyclic package dependency: package `{}` \ - depends on itself", - candidate.get_package_id()))) - } - let my_cx = try!(activate(my_cx, registry, &**candidate, method)); - if dep.is_transitive() { - cx.visited.borrow_mut().remove(candidate.get_package_id()); - } - match my_cx { - Ok(cx) => cx, - Err(e) => { last_err = Some(e); continue } - } + // If we hit an intransitive dependency then clear out the visitation + // list as we can't induce a cycle through transitive dependencies. + if !dep.is_transitive() { + my_cx.visited.borrow_mut().clear(); + } + let my_cx = match try!(activate(my_cx, registry, candidate, method)) { + Ok(cx) => cx, + Err(e) => { last_err = Some(e); continue } }; - match try!(activate_deps(my_cx, registry, parent, platform, deps, cur + 1)) { + match try!(activate_deps(my_cx, registry, parent, platform, deps, + cur + 1)) { Ok(cx) => return Ok(Ok(cx)), Err(e) => { last_err = Some(e); } } diff --git a/src/cargo/ops/cargo_compile.rs b/src/cargo/ops/cargo_compile.rs index 3e70b84c1..857c2094a 100644 --- a/src/cargo/ops/cargo_compile.rs +++ b/src/cargo/ops/cargo_compile.rs @@ -126,8 +126,6 @@ pub fn compile_pkg(package: &Package, options: &CompileOptions) (packages, resolved_with_overrides, registry.move_sources()) }; - debug!("packages={:?}", packages); - let to_build = match spec { Some(spec) => { let pkgid = try!(resolve_with_overrides.query(spec)); diff --git a/src/cargo/ops/cargo_read_manifest.rs b/src/cargo/ops/cargo_read_manifest.rs index 9c6b50b0d..7736bff4d 100644 --- a/src/cargo/ops/cargo_read_manifest.rs +++ b/src/cargo/ops/cargo_read_manifest.rs @@ -62,7 +62,6 @@ pub fn read_packages(path: &Path, source_id: &SourceId, config: &Config) if all_packages.is_empty() { Err(human(format!("Could not find Cargo.toml in `{}`", path.display()))) } else { - log!(5, "all packages: {:?}", all_packages); Ok(all_packages.into_iter().collect()) } } diff --git a/src/cargo/ops/cargo_rustc/mod.rs b/src/cargo/ops/cargo_rustc/mod.rs index 4b202c520..5d68db17c 100644 --- a/src/cargo/ops/cargo_rustc/mod.rs +++ b/src/cargo/ops/cargo_rustc/mod.rs @@ -129,8 +129,7 @@ pub fn compile_targets<'a, 'b>(env: &str, return Ok(Compilation::new(pkg)) } - debug!("compile_targets; targets={:?}; pkg={}; deps={:?}", targets, pkg, - deps); + debug!("compile_targets: {}", pkg); try!(links::validate(deps)); @@ -210,7 +209,7 @@ fn compile<'a, 'b>(targets: &[&'a Target], pkg: &'a Package, compiled: bool, cx: &mut Context<'a, 'b>, jobs: &mut JobQueue<'a, 'b>) -> CargoResult<()> { - debug!("compile_pkg; pkg={}; targets={:?}", pkg, targets); + debug!("compile_pkg; pkg={}", pkg); let _p = profile::start(format!("preparing: {}", pkg)); // Packages/targets which are actually getting compiled are constructed into diff --git a/src/cargo/util/graph.rs b/src/cargo/util/graph.rs index 22822f57d..9f97daa10 100644 --- a/src/cargo/util/graph.rs +++ b/src/cargo/util/graph.rs @@ -72,15 +72,15 @@ impl + Clone> Graph { } } -impl> fmt::Debug for Graph { +impl> fmt::Debug for Graph { fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result { try!(writeln!(fmt, "Graph {{")); for (n, e) in self.nodes.iter() { - try!(writeln!(fmt, " - {:?}", n)); + try!(writeln!(fmt, " - {}", n)); for n in e.iter() { - try!(writeln!(fmt, " - {:?}", n)); + try!(writeln!(fmt, " - {}", n)); } } diff --git a/tests/test_cargo_compile.rs b/tests/test_cargo_compile.rs index 43e7343c0..b164e5f85 100644 --- a/tests/test_cargo_compile.rs +++ b/tests/test_cargo_compile.rs @@ -754,7 +754,10 @@ test!(self_dependency { "#) .file("src/test.rs", "fn main() {}"); assert_that(p.cargo_process("build"), - execs().with_status(0)); + execs().with_status(101) + .with_stderr("\ +cyclic package dependency: package `test v0.0.0 ([..])` depends on itself +")); }); test!(ignore_broken_symlinks { @@ -1617,3 +1620,33 @@ Caused by: [..] ")); }); + +test!(cyclic_deps_rejected { + let p = project("foo") + .file("Cargo.toml", r#" + [package] + name = "foo" + version = "0.0.1" + authors = [] + + [dependencies.a] + path = "a" + "#) + .file("src/lib.rs", "") + .file("a/Cargo.toml", r#" + [package] + name = "a" + version = "0.0.1" + authors = [] + + [dependencies.foo] + path = ".." + "#) + .file("a/src/lib.rs", ""); + + assert_that(p.cargo_process("build").arg("-v"), + execs().with_status(101) + .with_stderr("\ +cyclic package dependency: package `foo v0.0.1 ([..])` depends on itself +")); +}); diff --git a/tests/test_cargo_freshness.rs b/tests/test_cargo_freshness.rs index 03107be6c..9b6c6cb55 100644 --- a/tests/test_cargo_freshness.rs +++ b/tests/test_cargo_freshness.rs @@ -28,6 +28,7 @@ test!(modifying_and_moving { assert_that(p.process(cargo_dir().join("cargo")).arg("build"), execs().with_status(0).with_stdout("")); p.root().move_into_the_past().unwrap(); + p.root().join("target").move_into_the_past().unwrap(); File::create(&p.root().join("src/a.rs")).write_str("fn main() {}").unwrap(); assert_that(p.process(cargo_dir().join("cargo")).arg("build"), -- 2.30.2